package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type MyNode struct {
	tree  *TreeNode
	depth int
}

func check(arr []*MyNode) bool {
	if len(arr) <= 1 {
		return true
	}
	i := 0
	j := len(arr) - 1
	for i < j {
		if arr[i].tree == nil && arr[j].tree == nil {
			i++
			j--
			continue
		}
		if arr[i].tree == nil && arr[j].tree != nil {
			return false
		}
		if arr[i].tree != nil && arr[j].tree == nil {
			return false
		}
		if arr[i].tree.Val != arr[j].tree.Val {
			return false
		}
		i++
		j--
	}
	return true
}

func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := []*MyNode{
		{tree: root, depth: 0},
	}
	level := []*MyNode{}
	for len(queue) > 0 {
		head := queue[0]
		queue = queue[1:]
		if head != nil {
			if len(level) > 0 {
				if level[len(level)-1].depth != head.depth {
					// 上一层遍历完毕
					if !check(level) {
						return false
					}
					level = []*MyNode{}
				}
			}
			level = append(level, head)
			// push to queue
			if head.tree != nil {
				queue = append(queue, &MyNode{tree: head.tree.Left, depth: head.depth + 1})
				queue = append(queue, &MyNode{tree: head.tree.Right, depth: head.depth + 1})
			}
		}
	}
	return check(level)
}

func main() {
	root := &TreeNode{Val: 1}
	n1 := &TreeNode{Val: 2}
	n2 := &TreeNode{Val: 2}
	n3 := &TreeNode{Val: 3}
	n4 := &TreeNode{Val: 4}
	root.Left = n1
	root.Right = n2
	n1.Left = n3
	n2.Right = n4
	println(isSymmetric(root))
}
